package leetcode.year2021.month11;

// 排序算法，快速排序、堆排序
public class _03_2FastSort {
  public void qsort(int arr[]){
    arr = qsortImpl(arr,0,arr.length-1);
  }

  private int[] qsortImpl(int[] arr, int left, int right) {
    if (left < right){
      int partitionIndex = partition(arr,left,right);
      qsortImpl(arr,left,partitionIndex - 1);
      qsortImpl(arr,partitionIndex + 1,right);
    }
    return arr;
  }

  private int partition(int[] arr, int left, int right){
    int pivot = left;
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
      if (arr[i] < arr[pivot]){
        swap(arr,i,index);
        index++;
      }
    }
    swap(arr,pivot,index-1);
    return index-1;
  }

  private void swap(int[] arr, int i, int index) {
    int temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;
  }

  // 垃圾快速排序实现方法一
//  public int[] qsortImpl(int arr[], int start, int end){
//    int scalar = arr[start];
//    int i = start;
//    int j = end;
//    while (i < j){
//      if (arr[i] < scalar) {
//        i++;
//      }
//      if (arr[j] > scalar){
//        j--;
//      }
//      if (arr[i] == arr[j] && i < j){
//        i++;
//      } else {
//        int temp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = temp;
//      }
//    }
//    if (i>start) arr = qsortImpl(arr,start, i-1);
//    if (i<end)arr = qsortImpl(arr,i+1, end);
//    return arr;
//  }
}
